package TreeTest;


import sun.reflect.generics.tree.Tree;

import javax.swing.*;
import java.util.*;

/*
* 搜索二叉树的设计模式
* AVL树：任何节点 左子树和右子树的高度差不要超过1
* 当右子树较大时 进行左旋  当左子树比较大时 进行右旋  |左旋和右旋的实现
* 每次添加节点后 从上而下查询节点平衡性是否违规 如果有违规，则调整
* 违规类型：
* LL型：左树的左子链高度较大  以左树根节点为新根进行右旋
* LR型：左树的右子链高度较大  先在左树上实行左旋 将整体变为LL型 然后整体右旋（永远让深度大的子树在外侧）
* RR型：右树的右子链高度较大  以右树根节点为新根进行左旋
* RL型：右树的左子链高度较大  先在右树上实行右旋 将整体变为RR型 然后整体左旋
* */
//接下来手写一棵AVL树  默认key为integer value为String
public class AVLTree {

    public class Node{
        Node parent;
        Node leftNode;      //左子节点
        Node rightNode;    //右子节点
        Integer key;   //在树中默认key唯一  不可以重复
        String value;
        int nodeNum;   //当前树下的节点数量 不包含当前节点

        public Node(Node parent,Node leftNode, Node rightNode, Integer key, String value) {
            this.parent = parent;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.key = key;
            this.value = value;
            nodeNum=0;
        }

        @Override
        public String toString() {
            return "Node{" +
                    ", key=" + key +
                    ", value='" + value + '\'' +
                    ", nodeNum=" + nodeNum +
                    '}';
        }
    }
        static class Dept{
            int maxDept;
            public Dept(int d){
                this.maxDept = d;
            }
        }

    private Node root;    //定义一个根节点

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    /*
    * 判断整个表是否为空
    * */
    public boolean isEmpty(){
        return isEmpty(root) == -1?true : false;
    }


    /*
    * 判断指定节点下是否为空   如果为空  返回-1  如果不为空 返回下面的节点数(不包含当前节点)
    * */
    public int isEmpty(Node node){
        int res=0;
        if (node == null || (node.leftNode==null && node.rightNode==null)){
            return -1;
        }
        if (node.leftNode!=null){
            res+=node.leftNode.nodeNum+1;
        }
        if (node.rightNode!=null){
            res+=node.rightNode.nodeNum+1;
        }
       return res;
    }

    /*
    * 判断是否存在指定key  并返回
    * */
    public Node contain(int key){
        return contain(root,key);
    }

    /*
    * 判断指定节点下是否存在指定key
    * */
    public Node contain(Node node , int key){
        if (node == null){
            return null;
        }
        if (node.key == key){
            return node;
        }
        if (node.key <key && node.rightNode!=null){
            return contain(node.rightNode,key);
        }
        if (node.key >key && node.leftNode!=null){
            return contain(node.leftNode,key);
        }
        return null;
    }

    /*
    * 返回树上key的最大节点
    * */
    public Node findMaxKey(){
        return findMaxKey(root);
    }

    /*
    * 返回指定节点下key的最大节点
    * */
    public Node findMaxKey(Node node){
        if (node.rightNode==null){
            return node;
        }
        return findMaxKey(node.rightNode);
    }

    /*
    * 返回树上最小的节点
    * */
    public Node findMinKey(){
        return findMinKey(root);
    }

    /*
    * 返回指定节点下key最小的节点
    * */
    public Node findMinKey(Node node){
        if (node.leftNode == null){
            return node;
        }
        return findMinKey(node.leftNode);
    }
    /*
    * 获得整棵树的最大深度
    * */
    public int getRootDept(){
        return getDept(root).maxDept;
    }

    /*
    * 获得指定节点下的最大深度
    * */
    public Dept getDept(Node node){
        if (node==null){
            return new Dept(0);
        }
        if (node.leftNode==null && node.rightNode==null){
            return new Dept(1);
        }
        return new Dept( (getDept(node.leftNode).maxDept>getDept(node.rightNode).maxDept
                ?getDept(node.leftNode).maxDept:getDept(node.rightNode).maxDept)+1);
    }

    /*
    * 插入一个新的键值对
    * */
    public void insertNode(int key,String value) {
        if (root==null){
            root=new Node(null,null,null,key,value);
            return;
        }
        if (contain(key)!=null){
            System.out.println("当前值已经存在，无法继续插入");
        }
        insertNode(key,value,root);
    }

    private void insertNode(int key,String value,Node node){
        if (node.key<key){
            if (node.rightNode==null){
                node.rightNode = new Node(node,null,null,key,value);
                reBalance(node.rightNode);
                return;
            }else {
            insertNode(key,value,node.rightNode);
            }
        }else if (node.key>key){
            if (node.leftNode==null){
                node.leftNode = new Node(node,null,null,key,value);
                reBalance(node.leftNode);
                return;
            }else {
            insertNode(key,value,node.leftNode);
            }
        }
    }

    /*
    * 删除指定key的节点 并返回其对应的value
    * */
    public String deleteNodeByKey(int key){
        Node node = contain(key);
        String str=node.value;
        if (node==null){
            System.out.println("当前key不存在");
            return null;
        }
        //如果该节点的孩子都为空
        if (node.leftNode==null && node.rightNode==null){
            node=null;
        }else if (node.leftNode!=null && node.rightNode==null){
            //如果只有左子树不为空
            Node left=findMaxKey(node.leftNode);
            node = left;
            left=null;
        }else {
            //如果只有右子树不为空 或者左右都不为空 则把右子树最小值挑上来进行替换
            Node right=findMinKey(node.rightNode);
            node = right;
            right=null;
        }
        return str;
    }


    /*
    * 根据指定的key去查询value值  不存在则返回空
    * */
    public String selectByKey(int key){
        Node node=contain(key);
        return node==null?null : node.value;
    }

    /*
    * 修改指定key的值为新value
    * */
    public void updata(int key,String value){
        Node node=contain(key);
        if (node==null){
            System.out.println("当前key不存在");
        }
        node.value=value;
    }

    /*
    * 返回一个所有key的集合
    * */
    public ArrayList<Node> getKeys(){
        return getKeys(root);
    }

    /*
    * 返回所有的节点的集合
    * */
    public ArrayList<Node> getKeys(Node node){
        ArrayList<Node> list=new ArrayList<>();
        if (node == null){
            return list;
        }
        list.addAll(getKeys(node.leftNode));
        list.add(node);
        System.out.println("加入:"+node.toString());
        list.addAll(getKeys(node.rightNode));
        return list;
    }

    /*
    *打印整个树 ， 使用中序遍历
    * */
    public void printTree(){
        ArrayList<Node> list = getKeys(root);
        Iterator<Node> it=list.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }

    /*
    * 对指定节点进行平衡性调整
    * */
    public void reBalance(Node node){
        //获得左右节点的高度
        /*
        如果高度差过2（需要判断对左还是对右进行调整）  则进行调整
         */
        int leftDept= getDept(node.leftNode).maxDept;
        int rightDept= getDept(node.rightNode).maxDept;
        int res = leftDept - rightDept;
        //如果<=1   则不调整 如果为2  则证明左子树高度大 进行左旋   如果为-2 则证明右子树高度大 进行右旋
        Node newN=null;
        if (res == 2){
            newN =moveToRight(node);
        }else if (res == -2){
            newN = moveToLeft(node);
        }
        if (newN==null){
            newN=node;
        }
        System.out.println("调节完毕,当前头节点为:"+newN.key );
        if (newN.parent!=null){
            reBalance(newN.parent);
        }
    }

    /*
    * 设计一个黑盒   将指定节点进行右旋转 返回新的头节点
    * */
    public Node moveToRight(Node node){
        Node father = node.parent;
        Node left = node.leftNode.leftNode;
        Node right = node.leftNode.rightNode;
        if ((left==null? 0: getDept(left).maxDept) < (right==null?0:getDept(right).maxDept)){
            moveToLeft(node.leftNode);
        }
        Node newHead = node.leftNode;
        newHead.rightNode = node;
        node.parent=newHead;
        node.leftNode = newHead.leftNode;

        if (newHead.leftNode!=null){
        newHead.leftNode.parent=node;
        }
        if ((father.key - newHead.key) > 0) {
            father.leftNode = newHead;
        } else {
            father.rightNode = newHead;
        }
        return newHead;
    }


    /*
    * 设计一个黑盒   将指定节点进行左旋转 返回新的头节点
    * */
    public Node moveToLeft(Node node){
        //左旋之前 首先判断右子树的左右子链哪个大  如果是左子链大 则需要先在右子树根节点的基础上进行右转
        Node father = node.parent;
        Node left = node.rightNode.leftNode;
        Node right = node.rightNode.rightNode;
        if ((left==null? 0: getDept(left).maxDept) > (right==null?0:getDept(right).maxDept)){
            moveToRight(node.rightNode);
        }

        /*Node newHead = node.leftNode;
        newHead.rightNode = node;
        node.parent=newHead;
        node.leftNode = newHead.rightNode;*/

        Node newHead = node.rightNode;
        newHead.leftNode = node;
        node.parent=newHead;
        node.rightNode = newHead.leftNode;
        //为新头节点处理父节点关系
        if (father!=null){
            if ( (father.key - newHead.key) < 0) {
                father.rightNode = newHead;
            } else {
                father.leftNode = newHead;
            }
        }
        return newHead;
    }

    /*
    * 宽度优先遍历
    * */
    public void printByWide(){
        if (root==null){
            System.out.println("结构为空");
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node node = queue.poll();
            System.out.println(node);
            if (node.leftNode!=null){
                queue.add(node.leftNode);
            }
            if (node.rightNode!=null){
                queue.add(node.rightNode);
            }
        }
    }
}
